Java知识体系

Appearance

Java集合_基础概念_补充内容02

1、Set集合是如何保证对象不重复的？ ​

HashSet 的底层采用HashMap来存放数据, 他执行添加元素操作的时候是将元素作为 Map 的Key；

HashMap保证key的不重复性，对于重复的key，HashMap会根据参数onlyIfAbsent的设置和原value是否为空两个条件来判断是否替换新value，

但要注意的是，对于HashSet，这个value只是个空的Object类的对象，没有任何实际作用，HashSet中的元素实际上是存储在key上的。针对重复的key，HashMap只有对于value的处理，并不会替换key，因此在HashSet中加入相同元素不会覆盖。

源码相关内容：

HashSet 的添加方法

public boolean add(E e) {  
    return map.put(e, PRESENT)==null;  
}

hashmap 的 put 方法

  public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());//----------1----------
        int i = indexFor(hash, table.length);//-----------2---------
        for (Entry e = table[i]; e != null; e = e.next) {//-----------3---------
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }//------------------4--------------------
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

当向HashMap中添加元素的时候，

  • 首先计算元素的hashcode值，然后根据1处的代码计算出Hashcode的值，
  • 再根据2处的代码计算出这个元素的存储位置，
    • 如果这个位置为空，就将元素添加进去；
    • 如果不为空，则看3-4的代码，遍历索引为i的链上的元素，如果key重复，则替换并返回oldValue值。

总结：结果向HashSet中加入相同元素不会进行覆盖。因为HashSet底层使用HashMap实现，元素存在HashMap的key中。在HashMap中，多次put相同的key，只会覆盖value，而不存在key的情况。

2、使用for循环删除元素陷阱 ​

先来看看下面这个程序：

public class Test {
 
	public static void main(String[] args) {
		List<String> list = new LinkedList<String>();
		list.add("A");
		list.add("B");
		list.add("C");
		
		for(int i=0; i<list.size(); i++){
			list.remove(i);
		}
		
		for(String item:list){
			System.out.println(item);
		}
	}
}

可以先猜猜这个程序输出什么？

按我们的思路，应该是输不出什么，但是执行它，输出的却是：B。

分析下这个程序，当第一步remove完后，集合内还剩2个元素，此时i为1，而list.size()的值为2，从0开始的话，i为1时，正好指向第二个元素，也就是说当remove完A后，直接就跳到C，将B漏了。

解决办法：

public class Test {
 
	public static void main(String[] args) {
		List<String> list = new LinkedList<String>();
		list.add("A");
		list.add("B");
		list.add("C");
		
		for(int i=0; i<list.size(); i++){
			list.remove(i);
			i -= 1;//每次删除完后，i减少1
		}
		
		for(String item:list){
			System.out.println(item);
		}
	}
}

3、讲述一下 length、length()、size() 的区别。 ​

  • java 中的 length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性.
  • java 中的 length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法.
  • java 中的 size() 方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!

4、在 HashMap 中，为什么不一下子把整个链表变为红黑树呢 ​

为什么非要等到链表的长度大于等于8的时候，才转变成红黑树？

（1）构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。

（2）HashMap频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率。